package 开始的算法算法入门8月.广度优先搜索深度优先搜索;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;
// https://leetcode-cn.com/problems/rotting-oranges/
public class 腐烂的橘子9940820 {
    class Solution {
        int[] dr = new int[]{-1, 0, 1, 0};
        int[] dc = new int[]{0, -1, 0, 1};

        public int orangesRotting(int[][] grid) {
            int R = grid.length, C = grid[0].length;
            Queue<Integer> queue = new ArrayDeque<Integer>();
            Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
            for (int r = 0; r < R; ++r) {
                for (int c = 0; c < C; ++c) {
                    if (grid[r][c] == 2) {
                        int code = r * C + c;
                        queue.add(code);
                        depth.put(code, 0);
                    }
                }
            }
            int ans = 0;
            while (!queue.isEmpty()) {
                int code = queue.remove();
                int r = code / C, c = code % C;
                for (int k = 0; k < 4; ++k) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        int ncode = nr * C + nc;
                        queue.add(ncode);
                        depth.put(ncode, depth.get(code) + 1);
                        ans = depth.get(ncode);
                    }
                }
            }
            for (int[] row: grid) {
                for (int v: row) {
                    if (v == 1) {
                        return -1;
                    }
                }
            }
            return ans;
        }
    }

}
